## Script for factoring X^n-1 over K


from PyM import *


def cyclotomic_splitting(n,K=Zn(2)):
    q = cardinal(K)
    m = order(q,n)
    f=get_irreducible_polynomial(K,m,'x')
    x = variable(f)
    [F,t] = extension(K,f,'t','F')
    r = (q**m-1)//n
    a = primitive_root(F)
    w = a**r
    show('order(w) =',order(w))
    C = cyclotomic_classes(n,q)
    return [product([(x-w**j) for j in c]) for c in C]

    
types_off()
n=11; K=Zn(3)

show(cyclotomic_splitting(n,K))

[_,x]=polynomial_ring(Z_, 'X')

show(factor(x**n-1,K))

S = cyclotomic_splitting(17,Zn(13))

show(S)

#show(factor(x**17-1,Zn(13)))